/**
 * @author João Luís Palma Cardeira - hippie.stereo@gmail.com
 * @version 1.0
 * @date 06/06/2013
 * @copyright (C) :-)
 * @note Applicação para o trabalho de EDA 2012/2013
 * @see main : RunApp
 */
class HeapSortCLS
{

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int intHeapSize = 0;
	private double ListaDados[];

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	protected void Sort(double[] listaIn)
	{
		ListaDados = listaIn;
		intHeapSize = ListaDados.length;
		
		BuildMaxHeap();
		
		for(int IncCount = ListaDados.length - 1; IncCount >= 0; IncCount--)
		{
			double temp = ListaDados[0];
			ListaDados[0] = ListaDados[IncCount];
			ListaDados[IncCount] = temp;
			setHeapSize(getHeapSize() - 1);
			MaxHeapify(0);
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void MaxHeapify(int intIn)
	{	
		int l = leftNode(intIn);
		int r = rightNode(intIn);
		int largest;
		
		if(l <= getHeapSize() && ListaDados[l] > ListaDados[intIn])
		{largest = l;}
		else
		{largest = intIn;}
		
		if(r <= getHeapSize() && ListaDados[r] > ListaDados[largest])
		{largest = r;}
		
		if(largest != intIn)
		{
			double temp = ListaDados[intIn];
			ListaDados[intIn] = ListaDados[largest];
			ListaDados[largest] = temp;
			MaxHeapify(largest);
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void BuildMaxHeap()
	{	
		setHeapSize(ListaDados.length - 1);
		
		for(int IncCount = ((ListaDados.length - 1)/2); IncCount >= 0; IncCount--)
		{
			MaxHeapify(IncCount);
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private double HeapMaximum()
	{
		return ListaDados[1];
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private double ReturnExtractMax()
	{
		double max = 0;

		if(getHeapSize() < 1)
		{
			System.out.println("\n\nHEAP UNDERFLOW\n\n");
		}

		max = ListaDados[1];
		ListaDados[1] = ListaDados[getHeapSize()];
		setHeapSize(getHeapSize() - 1);
		MaxHeapify(1);

		return max;
	}	
	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void HeapIncreaseKey(int i, int key)
	{
		if (key < ListaDados[i])
		{
			System.out.println("\n\nNEW KEY IS SMALLER\n\n");
		}

		ListaDados[i] = key;

		while (i > 1 && ListaDados[_parentNode(i)] < ListaDados[i])
		{
			double temp = ListaDados[i];
			ListaDados[i] = ListaDados[_parentNode(i)];
			ListaDados[_parentNode(i)] = temp;
			i = _parentNode(i);
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void MaxHeapInsert(int key)
	{
		setHeapSize(getHeapSize() + 1);
		ListaDados[getHeapSize()] = -99999;
		HeapIncreaseKey(getHeapSize(), key);
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int _parentNode(int intIn)
	{
		return (intIn/2) + 1;
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int leftNode(int intIn)
	{
		return (intIn*2) + 1;
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int rightNode(int intIn)
	{
		return (intIn*2) + 2;
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void setHeapSize(int intIn)
	{
		intHeapSize = intIn;
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int getHeapSize()
	{
		return intHeapSize;
	}	
}